package com.lyj.sc.aliyuntianchi.test20220715;

/**
 * @program: code-random
 * @description:
 * @author: lyj
 * @create: 2022-07-15 10:11
 * @version: 1.0
 * @Modifier By:
 **/
public class test3 {
    public ListNode sortList(ListNode head) {
        return  sort(head,null);
    }
    public ListNode sort(ListNode head,ListNode tail){
        if(head==null){
            return head;
        }
        if(head.next==tail){
            // 在下面双指针找中点的时候，是有可能出现 head 和tail在一个节点上，所以要将head.next=null
            head.next=null;
            return head;
        }
        //双指针
        ListNode slow = head;
        ListNode fast = head;
        while (fast!=tail){
            slow=slow.next;
            fast=fast.next;
            if(fast!=tail){
                fast=fast.next;
            }
        }
        ListNode mid = slow;
        ListNode l1 = sort(head,mid);
        ListNode l2 = sort(mid,tail);
        return mergeTwoLists(l1,l2);
    }
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        //合并两个有序链表
        ListNode dummyNode = new ListNode(0);
        ListNode current = dummyNode;
        while (list1!=null && list2!=null){
            if(list1.val>list2.val){
                current.next=new ListNode(list2.val);
                list2=list2.next;
            }else {
                current.next=new ListNode(list1.val);
                list1=list1.next;
            }
            current=current.next;
        }
        if(list1!=null){
            current.next=list1;
        }
        if(list2!=null){
            current.next=list2;
        }
        return dummyNode.next;
    }


}
